package offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class offer_0034 {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> list=new LinkedList<>();
        List<Integer> path=new LinkedList<>();
        int[] sum=new int[1];

        if(root==null) return list;
        sum[0]=root.val;
        path.add(root.val);
        sum(list,path,root,targetSum,sum);
        return list;
    }
    public void sum(List<List<Integer>> list, List<Integer> path, TreeNode node, int targetSum, int[] sum){
        if(node.left==null&&node.right==null){
            if(sum[0]==targetSum){
                list.add(new ArrayList<>(path));
            }
            return;
        }
        if(node.left!=null){
            path.add(node.left.val);
            sum[0]+=node.left.val;
            sum(list,path,node.left,targetSum,sum);
            sum[0]-=node.left.val;
            path.remove(path.size()-1);
        }
        if(node.right!=null){
            path.add(node.right.val);
            sum[0]+=node.right.val;
            sum(list,path,node.right,targetSum,sum);
            sum[0]-=node.right.val;
            path.remove(path.size()-1);
        }
    }
}
